class TreeNode(object):
    """二叉树概念：
    根节点：位于二叉树顶层的节点，没有父节点
    叶节点：没有子节点的节点，其两个指针均指向None
    边：连接两个节点的线段，即节点引用
    节点所在的层：从顶至底递增，根节点所在层为1
    节点的度：节点的子节点的数量；二叉树中取值范围为0/1/2
    二叉树的高度：从根节点到最远叶节点所经过的边的数量
    节点的深度：从根节点到该节点所经过的边的数量
    节点的高度：从距离该节点最远的叶节点到该节点所经过的边的数量
    """
    def __init__(self, val: int):
        # 节点值
        self.val = val
        # 左子节点
        self.left = None
        # 右子节点
        self.right = None

if __name__ == '__main__':
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    # 插入与删除节点
    p = TreeNode(0)
    # 在n1->n2中间插入节点P
    n1.left = p
    p.left = n2

    # 删除节点p
    n1.left = n2

    """
    # 常见二叉树类型
    1. 完美二叉树
        所有层的节点都被完全填满，叶节点的度为0，其余所有节点的度为2；如果树高为h，则节点总数为2^(h+1)-1
    2. 完全二叉树
        只有最底层的节点未被填满，且最底层节点尽量靠左填充
    3. 完满二叉树
        除叶节点之外，其余所有节点都有两个子节点
    4. 平衡二叉树
        任意及诶单的左子树和右子树的高度之差的绝对值不超过1
    """